package 贪心算法;

import java.util.Arrays;
import java.util.LinkedList;

public class 根据身高重建队列 {

    public static int[][] reconstructQueue(int[][] people) {
        sort(people);
        int n = people.length;
        int[][] res = new int[n][];
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < n; i++) {
           linkedList.add(i);
        }
        for (int i = 0; i < n; i++) {
            int k = people[i][1];
            int index = linkedList.get(k);
            res[index] = people[i];
            linkedList.remove((Object)index);
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] people = {{7,0},{4,4},{7,1},{5,0},{6,1},{5,2}};
        int[][] x = reconstructQueue(people);
        for (int[] ints : x) {
            System.out.println(Arrays.toString(ints));
        }

    }

    private static int[][] sort(int[][] num){
        return sort(num,0,num.length-1);
    }

    private static int[][] sort(int[][] num,int start,int end){
        if (start >= end){
            return num;
        }
        int v = num[start][0];
        int v1 = num[start][1];
        int i = start+1;
        int j = end;
        int it = start;
        while (i <= j){
            if (num[i][0] < v || (num[i][0] == v && num[i][1] > v1)){
                int[] temp = num[i];
                num[i] = num[it];
                num[it] = temp;
                it++;
                i++;
            }else if (num[i][0] == v && num[i][1] == v1){
                i++;
            }else {
                while (j > i && num[j][0] > v){
                    j--;
                }
                int[] temp = num[i];
                num[i] = num[j];
                num[j] = temp;
                j--;
            }
        }
        sort(num,start,it-1);
        sort(num,j+1,end);
        return num;
    }


}
